package leetcode_周赛._2023._11;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 第 371 场周赛
 * AC_3
 *
 * @author yezh
 * @date 2023/11/12 20:42
 */
public class _12 {

    /**
     * 2934. 最大化数组末位元素的最少操作次数
     * 算法: 脑筋急转弯
     */
    public int minOperations(int[] nums1, int[] nums2) {
        int n = nums1.length, last1 = nums1[n - 1], last2 = nums2[n - 1];
        int ans = Math.min(operation(nums1, nums2, last1, last2), operation(nums1, nums2, last2, last1) + 1);
        return ans == n + 1 ? -1 : ans;
    }

    int operation(int[] nums1, int[] nums2, int last1, int last2) {
        int n = nums1.length, res = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums1[i] > last1) {
                if (nums1[i] > last2 || nums2[i] > last1) return n + 1;
                ++res;
            } else if (nums2[i] > last2) {
                if (nums2[i] > last1 || nums1[i] > last2) return n + 1;
                ++res;
            }
        }
        return res;
    }


    /**
     * 2935. 找出强数对的最大异或值 II
     * 算法: 位运算 + 哈希表
     */
    public int maximumStrongPairXor(int[] nums) {
        Arrays.sort(nums);
        // |x - y| <= min(x, y) ==> y - x <= x ==> y <= 2 * x
        int max = 0;
        for (int num : nums) max = Math.max(num, max);
        int ans = 0, mask = 0, highBit = 31 - Integer.numberOfLeadingZeros(max);
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = highBit, newAnswer, x; i >= 0; i--) {
            seen.clear();
            mask |= (1 << i);
            newAnswer = ans | mask;
            for (int num : nums) {
                x = num & mask;
                if (seen.containsKey(newAnswer ^ x) && 2 * seen.get(newAnswer ^ x) >= num) {
                    ans = newAnswer;
                    break;
                }
                seen.put(x, num);
            }
        }
        return ans;
    }

}
